Two men are arrested, but the police do not possess enough information for a conviction. The police separate the two men and offer each the same deal- if one testifies against his partner (betrays), and the other stays quiet (doesn't betray), the betrayer goes free and the non-betrayer receives the full one-year sentence. If both remain silent, both are sentenced to only one month in jail for a minor charge. If each 'rats out' the other, each receives a three-month sentence. Each prisoner must choose to either betray or remain silent; the decision of each is kept quiet. What should they do?
The outcomes for player 1 are:
Player 2 move: Betray Don't Betray Player 1 move: --------------------+------------------------ Betray | -3 0 --------------------+------------------------ Don't Betray | -12 -1 --------------------+------------------------
Observe that for both player 1 and player 2, the "right" thing to do is to betray, since that avoids the possibility of -12. But of course if nobody betrays, they both wind up with only a month in jail-- a better outcome!
This problem has been the subject of much discussion and research. Let's take a look at a small piece of the problem.
;; DATA DEFINITIONS ;; A Move is one of ;; -- "betray" ;; -- "don't betray" ;; move-fn : Move -> ??? ;; (define (move-fn m) ;; (cond ;; [(string=? m "betray") ...] ;; [(string=? m "don't betray") ...]))
Here's the task:
;;; outcome : Move Move -> Number ;;; GIVEN: the moves of player 1 and player 2 ;;; RETURNS: the outcome for player 1 ;;; EXAMPLES: (outcome "betray" "don't betray") = 0. ;;; see table above.
Here's how NOT to do it:
(define (outcome move1 move2) (cond [(string=? move1 "betray") (cond [(string=? move2 "betray") -3] [(string=? move2 "don't betray") 0])] [(string=? move1 "don't betray") (cond [(string=? move2 "betray") -12] [(string=? move2 "don't betray") -1])])) ;; TESTS: (begin-for-test (check-equal? (outcome "betray" "betray") -3) (check-equal? (outcome "betray" "don't betray") 0) (check-equal? (outcome "don't betray" "betray") -12) (check-equal? (outcome "don't betray" "don't betray") -1))
This code does NOT follow the template for structural decomposition. It starts out doing structural decomposition on move1, but in structural decomposition, the right-hand side of each cond can only be function composition, and here the code has inserted a second structural decomposition (on move2).
Rewrite this code to follow the template by splitting each of the right-hand sides into a separate help function. Be sure to use good function names for your help functions.
Last modified: Sun Sep 14 12:11:23 Eastern Daylight Time 2014